進入到這篇之前要先確保大家有一些概念。
大家要知道Innodb各個資料頁物理上並沒有連在一起，而是透過FIL_PAGE_PREV和FIL_PAGE_NEXT屬性串連起來，形成一個雙向鏈結串列。而每個資料頁內的紀錄會按照主鍵值從小到大的順序形成一個單向鏈結串列，每個資料頁都會為儲存在它裡面的紀錄生成一個頁目錄，在透過主鍵搜尋某筆紀錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然後在歷遍該槽對應分組中的紀錄即可快速找到指定的紀錄。
額外補充說明：有些蛙友可能對二分法有點疑惑？就是我們在前文有舉一個例子搜尋主鍵值為6的紀錄，我們會拿6去跟中間槽對應的主鍵值比對大小，找到high為2，low為1，這就是二分法。
如果對於我前面內容有一丁點不清楚的，請先去前面複習再來唷
那就進入今日的正題 -- 索引 --
我們先了解沒有索引的時候，會是怎麼搜尋資料的。
如果以主鍵為搜尋條件，我們知道可以透過二分法比對主鍵值找尋對應的槽，大大的提升搜尋的速度。
但如為非主鍵的搜尋條件，就只能照最原先做法一筆一筆比對，效率低落。
大多數產品表的資料量都非常大，需要相當多資料頁來儲存。
在沒有索引的情況下，我們無法快速的定位到查詢紀錄所在的頁，因此只能從第一頁沿著雙向鏈結串列往下找，並在每頁一筆一筆去比對資料，執行效率真的非常差呀...
該如何改善呢？？？
有兩個具體步驟：
所以實際上新增一筆紀錄X到資料頁B的時候，如果發現此紀錄X比上一資料頁A的紀錄Y還小，則會將資料頁A較大的那筆紀錄Y移動到資料頁B(騰出空間)，而較小的紀錄X則是新增到資料頁A裡面去，確保資料頁B的所有紀錄主鍵值都大於資料頁A。這個動作也叫做頁分裂。
透過這樣的方式確保符合規律。
之所以稱其為簡易目錄，是因為並不完善，有些問題待解決。
1.Innodb使用頁作為管理儲存空間的基本單位，因為頁與頁間並不會都是連在一起的(只是透過next_record的方式串連在一起)，所以在一頁內最多就是16kb的連續儲存空間，當目錄項非常多的時候就就容納不下。
2.再來我們常常需要對資料做新增、刪除、修改的動作，如果有個目錄A內容只包含一個頁面B的索引(只有一筆key跟page_no)，當頁面B紀錄全部刪除之後，那這目錄A也沒有存在的必要了(都沒紀錄了幹嘛浪費時間去頁面B)。這時我們刪除了目錄A，由於目錄在物理記憶體上是連續儲存的，所以其後的所有目錄都要往前挪。可想而知這樣牽一髮而動全身的方式實在是很沒有效率啊。
有鑑於此，Innodb的工程師思考有沒有更好可以靈活管理目錄項的方式？
仔細觀察可以發現目錄項其實跟使用者紀錄蠻相似的，只是裡面存放的資料不一樣，目錄項是儲存該資料頁最小的主鍵值(key)及頁號(page_no)，而使用者紀錄是儲存真實資料。
前面的問題是受限於目錄項要儲存在連續物理記憶體上，最多就只能16kb。
但如果我們把目錄項跟使用者紀錄一樣存在資料頁呢？
當然一頁還是最多只能容納16kb，但我們可以一樣畫葫蘆為其再製作更進階的目錄項[往上再多一階(層)]，並隨著資料變多，這個目錄的層級可以不斷地往上長。
整個資料結構會變成像一個B+樹
所有的使用者紀錄都是存放在最底層的節點上（稱為葉子節點或葉節點）
底層以上都是用來存放目錄項紀錄的節點（稱為非葉子節點或內節點）
其中最上面的那個節點稱為根節點。
這樣子就不會有目錄項過多容納不下的問題，且也不太會有刪除某個目錄就一定要將其後所有的目錄都挪動的情況（應還是有部分的資料需要調動，但減少了挪動的情況，提升了效能）。
是不是很不錯！！！因此就採用了這樣的做法。
整個搜尋的流程變成先透過最上層的進階目錄項找到對應的低階目錄項，再透過低階的目錄項找到對應的資料頁，最後再去資料頁歷遍找到指定的紀錄。
最後補充說明一下實際上使用者紀錄跟目錄項紀錄的屬性差異在那？
目錄項紀錄跟普通使用者紀錄，除了以上三個地方不一樣之外就沒有差別了。
今日難度開始提高，但還是希望大家耐著性子把它一個個熟悉看懂了，加油！
有任何不清楚的地方隨時歡迎提問唷～我會盡我所能回答。
而有任何錯誤的地方也歡迎提醒我改正唷！
iThome鐵人賽
看影片追技術